package com.zhhe.leetcode;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 数组
 */
public class LeetCodeArray {
    /**
     * 27、移除元素
     */
    public static int removeElement(int[] nums, int val) {
        //1、暴力解法
//        int size = nums.length;
//        for (int i = 0; i < size; i++) {
//            if (nums[i] == val) {
//                for (int j = i + 1; j < size; j++) {
//                    nums[j - 1] = nums[j];
//                }
//                i--;
//                size--;
//            }
//        }
//        return size;

        //2、双指针法
        int low = 0;
        for (int high = 0; high < nums.length; high++) {
            if (nums[high] != val) {
                nums[low++] = nums[high];
            }
        }
        return low;
    }

    /**
     * 977、有序数组的平方
     */
    public static int[] sortedSquares(int[] nums) {
        //1、暴力解法(先平方，再排序)
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = nums[i] * nums[i];
//        }
//        SortAlgorithm.quickSort(nums, 0 , nums.length - 1);
//        return nums;

        //2、双指针法
        int[] arr = new int[nums.length];
        int low = 0, high = nums.length - 1, k = nums.length - 1;
        while (low <= high) {
            if (nums[low]*nums[low] > nums[high]*nums[high]) {
                arr[k] = nums[low]*nums[low];
                low++;
                k--;
            } else {
                arr[k] = nums[high]*nums[high];
                high--;
                k--;
            }
        }
        return arr;
    }

    /**
     * 209、长度最小的子数组
     */
    public static int minSubArrayLen(int target, int[] nums) {
        //1、暴力破解
//        int result = Integer.MAX_VALUE;
//        int sum = 0;
//        int subLength = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum = 0;
//            for (int j = i; j < nums.length; j++) {
//                sum+=nums[j];
//                if (sum >= target) {
//                    subLength = j - i + 1;
//                    result = result < subLength ? result : subLength;
//                    break;
//                }
//            }
//        }
//        return result == Integer.MAX_VALUE ? 0 : result;

        //2、滑动窗口
//        int result = Integer.MAX_VALUE;
//        int i = 0, sum = 0, subLength = 0;
//        for (int j = 0; j < nums.length; j++) {
//            sum += nums[j];
//            while (sum >= target) {
//                subLength = j - i + 1;
//                result = result < subLength ? result : subLength;
//                sum -= nums[i++];
//            }
//        }
//        return result == Integer.MAX_VALUE ? 0 : result;

        //3、前缀+二分查找
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int[] sums = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 0; i <= length ; i++) {
            int s = target + sums[i];
            int index = Arrays.binarySearch(sums, s);
            if (index < 0) {
                index = ~index;
            }
            if (index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    /**
     * 59、螺旋矩阵2
     */
    public static int[][] generateMatrix(int n) {
        //注意坚持左闭右开原则
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {

            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] vec = new int[n];
        int[] p = new int[n];

        int presum = 0;
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
            presum += vec[i];
            p[i] = presum;
        }

        while (scanner.hasNextInt()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int sum;
            if (a == 0) {
                sum = p[b];
            } else {
                sum = p[b] - p[a - 1];
            }
            System.out.println(sum);
        }

        scanner.close();
    }
}
